// https://www.lintcode.com/problem/split-array/

public class Solution {
    /**
     * @param arr: an inter array 
     * @return: return the min sum
     */
    public int splitArray(int[] arr) {
        // write your code here
        List<ArrayList<Integer>> nums = new ArrayList<>();
        for (int i = 1; i < arr.length - 1; ++i) {
            if (nums.size() < 3) {
                ArrayList<Integer> v = new ArrayList<>();
                v.add(arr[i]);
                v.add(i);
                nums.add(v);
                Collections.sort(nums, (ArrayList<Integer> v1, ArrayList<Integer> v2) -> (v1.get(0) - v2.get(0)));
            } else {
                for (int j = 2; j >= 0; --j) {
                    if (nums.get(j).get(0) > arr[i]) {
                        nums.get(j).set(0, arr[i]);
                        nums.get(j).set(1, i);
                        Collections.sort(nums, (ArrayList<Integer> v1, ArrayList<Integer> v2) -> (v1.get(0) - v2.get(0)));
                        break;
                    }
                }
            }
        }
        Collections.sort(nums, (ArrayList<Integer> v1, ArrayList<Integer> v2) -> (v1.get(1) - v2.get(1)));
        Integer v1 = Integer.MAX_VALUE;
        Integer v2 = v1;
        Integer v3 = v1;
        if ((nums.get(1).get(1) - nums.get(0).get(1)) > 1) {
            v1 = nums.get(0).get(0) + nums.get(1).get(0);
        }
        v2 = nums.get(0).get(0) + nums.get(2).get(0);
        if ((nums.get(2).get(1) - nums.get(1).get(1)) > 1) {
            v3 = nums.get(1).get(0) + nums.get(2).get(0);
        }
        return Math.min(Math.min(v1, v2), v3);
    }
}